Search for: All records

This paper introduces Otti, a general-purpose com- piler for (zk)SNARKs that provides support for numerical op- timization problems. Otti produces efficient arithmetizations of programs that contain optimization problems including linear programming (LP), semi-definite programming (SDP), and a broad class of stochastic gradient descent (SGD) instances. Numerical optimization is a fundamental algorithmic building block: applications include scheduling and resource allocation tasks, approximations to NP-hard problems, and training of neural networks. Otti takes as input arbitrary programs written in a subset of C that contain optimization problems specified via an easy-to-use API. Otti then automatically produces rank-1 constraint satisfiability (R1CS) instances that express a succinct transformation of those programs. Correct execution of the transformed program implies the optimality of the solution to the original optimization problem. Our evaluation on real benchmarks shows that Otti, instantiated with the Spartan proof system, can prove the optimality of solutions in zero-knowledge in as little as 100 ms—over 4 orders of magnitude faster than existing approaches. 

Abstract The map is a weak equivalence. 

For an equivariant commutative ring spectrum R, \pi_0 R has algebraic structure reflecting the presence of both additive transfers and multiplicative norms. The additive structure gives rise to a Mackey functor and the multiplicative structure yields the additional structure of a Tambara functor. If R is an N_\infty ring spectrum in the category of genuine G-spectra, then all possible additive transfers are present and \pi_0 R has the structure of an incomplete Tambara functor. However, if R is an N_\infty ring spectrum in a category of incomplete G-spectra, the situation is more subtle. In this chapter, we study the algebraic theory of Tambara structures on incomplete Mackey functors, which we call bi-incomplete Tambara functors. Just as incomplete Tambara functors have compatibility conditions that control which systems of norms are possible, bi-incomplete Tambara functors have algebraic constraints arising from the possible interactions of transfers and norms. We give a complete description of the possible interactions between the additive and multiplicative structures. 

Let p∈Z be an odd prime. We prove a spectral version of Tate–Poitou duality for the algebraic K-theory spectra of number rings with p inverted. This identifies the homotopy type of the fiber of the cyclotomic trace K(OF)∧p→TC(OF)∧p after taking a suitably connective cover. As an application, we identify the homotopy type at odd primes of the homotopy fiber of the cyclotomic trace for the sphere spectrum in terms of the algebraic K-theory of Z. 

For N∞ operads O and O' such that there is an inclusion of the associated indexing systems, there is a forgetful functor from incomplete Tambara functors over O' to incomplete Tambara functors over O. Roughly speaking, this functor forgets the norms in O' that are not present in O. The forgetful functor has both a left and a right adjoint; the left adjoint is an operadic tensor product, but the right adjoint is more mysterious. We explicitly compute the right adjoint for finite cyclic groups of prime order.